//给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
//
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
//
// 此外，你可以假设该网格的四条边均被水包围。
//
//
//
// 示例 1：
//
//
//输入：grid = [
//  ["1","1","1","1","0"],
//  ["1","1","0","1","0"],
//  ["1","1","0","0","0"],
//  ["0","0","0","0","0"]
//]
//输出：1
//
//
// 示例 2：
//
//
//输入：grid = [
//  ["1","1","0","0","0"],
//  ["1","1","0","0","0"],
//  ["0","0","1","0","0"],
//  ["0","0","0","1","1"]
//]
//输出：3
//
//
//
//
// 提示：
//
//
// m == grid.length
// n == grid[i].length
// 1 <= m, n <= 300
// grid[i][j] 的值为 '0' 或 '1'
//
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组与矩阵 矩阵 👍 2191 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
//? 此题dfs 思路是找联通的1
function numIslands(grid: string[][]): number {
    //? 定义方位 顺序为下右上左
    const moveX = [0, 1, 0, -1];
    const moveY = [1, 0, -1, 0];

    if (grid.length === 0 || grid[0].length === 0) return 0;

    //? 初始化岛屿数量，缓存二维数组的行数与列数
    let count = 0;
    const row = grid.length;
    const column = grid[0].length;
    //? 找寻连通的1
    const dfs = function (i: number, j: number) {
        //? 如果试图探索的范围已经越界，则return  下右上左寻找找不到1 说明岛屿形成 此dfs会退出
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === "0") return;
        //? 探索过的1和原本的0都置为0
        grid[i][j] = "0";

        //? 遍历完当前的1，继续去寻找下一个1，顺序为下右上左
        for (let k = 0; k < 4; k++) {
            dfs(i + moveX[k], j + moveY[k]);
        }
    };

    for (let i = 0; i < row; i++) {
        for (let j = 0; j < column; j++) {
            if (grid[i][j] === "1") {
                dfs(i, j);
                //? dfs返回 必然会出现岛屿 此次出现的岛屿都会置0 不再参与计算
                count++;
            }
        }
    }

    return count;

};
//leetcode submit region end(Prohibit modification and deletion)
